package demo.DataStrucAndAlgo.Sort;

import java.util.Arrays;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/27-07-27-9:26
 * @Description：demo.DataStrucAndAlgo.Sort   快速排序
 */
/*快速排序
    先把数组中的一个数当作基准数，一般会把数组中最左边的数当作基准数，然后从两边进行检索，
    先从右边(j)检索比基准数小的，再从左边(i)检索比基准数大的，如果检索到了就停下，然后交换这两个元素，
    然后再继续检索,i和j一旦相遇就停止检索，把基准数和相遇位置的元素交换，基准数和相遇位置的数交换完成，表示第一轮排序结束；
    特点：基准数左边都比他小，右边都比他大
    以后先排基准数左边，排完之后再排基准数右边，方式和第一轮一样

 */
public class QuickSort {
    public static void main(String[] args) {
        int[] data = {6,1,2,7,9,3,4,5,10,8};
//        int[] data = {6,1};
        quickSort(data,0,data.length-1);
        System.out.println(Arrays.toString(data));
    }

    public static void quickSort(int[] data, int left, int right) {
        if(left>right){         //左索引大于右索引时，不合法跳出
            return;
        }
        int pivot = data[left];     //以最左边的数据作为基准
        int temp;     //临时交换变量
        int l = left;  // 左索引
        int r = right;   //右索引
        while (l <= r) {
            //当l!=r时，说明一轮排序左右还没排完
            while (data[r]>=pivot && r>l){  //在左右索引不重合时进行搜索，重合时，暂停右移动
                //右索引负责寻找右边小于基准的数据
                r--;   //右索引左移
            }
            while(data[l] <= pivot && l<r){   //只有在左右索引不重合时进行搜索，重合时，暂停左移动
                //左索引负责寻找左边大于基准的数据
                l++;
            }
            if(l<r){             //找到要交换的值了
                temp = data[l];
                data[l] = data[r];
                data[r] = temp;
            }else{
                data[left] = data[l];     //基准数与重合位置交换
                data[l] = pivot;
                quickSort(data,left,--r);   //左递归
                quickSort(data,++l,right);  //右递归  // 0,1
            }
        }
    }
}
